备用返回通道

转到题目

题目描述：

小红定义一个字符串的权值为该字符串中 “01” 子序列的数量。

现在小红拿到了一个由字符 ‘0’ 和 ‘1’ 组成的字符串环（即最后一个字符下一个是第一个字符）。小红想知道，这个环的所有长度不小于 2 的连续子串的权值之和是多少？

由于答案可能很大，请将答案对 (10^9 + 7) 取模后输出。

“01” 子序列 是从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串，且该新字符串恰好是 “01”。

子串 是从原字符串中，连续选择一段字符（可以全选、可以不选）得到的新字符串。在本题中，环上的子串是任取两个下标 ( l ) 和 ( r )，从 ( l ) 不断向右取直到 ( r ) 形成的连续子串；特殊的是，若 ( r < l )，则会从 ( l ) 向右取到最后一个字符，之后从第一个字符取到 ( r )。

输入描述：

• 第一行输入一个正整数 ( n ) (( 1 \leq n \leq 10^5 )) 代表字符串的长度。
• 第二行输入一个长度为 ( n )，由字符 ‘0’ 和 ‘1’ 构成的字符串 ( s )。

输出描述：

• 输出一个整数，代表所有长度不小于 2 的连续子串的权值之和。由于答案可能很大，请将答案对 ( 10^9 + 7 ) 取模后输出。

示例1：

输入：

3
001

输出：

4

解释： 在这个样例中，长度为 2 的连续子串有 3 个：

• “00”，权值为 0；
• “01”，权值为 1；
• “10”，权值为 0。

长度为 3 的连续子串有 3 个：

• “001”，权值为 2；
• “010”，权值为 1；
• “100”，权值为 0。

所有长度不小于 2 的连续子串的权值之和为： ( 0 + 1 + 0 + 2 + 1 + 0 = 4 )。